/*
Date:20220117 14:03PM
key:就是统计出链表的size。然后,链表走到rand()%size就return。时间复杂度O(n)，空间O(1).
 */
class Solution {
public:
    //static vector<int>v;
    ListNode*p1;
    int size;
    Solution(ListNode* head) {
        p1=head;
        ListNode* p=head;
        int i=0;
        while(p!=nullptr)
        {
            i++;
            p=p->next;
        }
        size=i;
    }
    
    int getRandom() {
        
        int random=rand()%size;
        int i=0;
        //cout<<random;
        ListNode* p=p1;
        while(i!=random)
        {
            i++;
            p=p->next;
        }
        return p->val;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(head);
 * int param_1 = obj->getRandom();
 */